package com.michael.leetcode;

import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

@Slf4j
public class CountAndSay_38 {

    /*38. 外观数列
    「外观数列」是一个数位字符串序列，由递归公式定义：
    countAndSay(1) = "1"
    countAndSay(n) 是 countAndSay(n-1) 的行程长度编码。
    行程长度编码（RLE）是一种字符串压缩方法，其工作原理是通过将连续相同字符（重复两次或更多次）替换为字符重复次数（运行长度）和字符的串联。
    例如，要压缩字符串 "3322251" ，我们将 "33" 用 "23" 替换，将 "222" 用 "32" 替换，将 "5" 用 "15" 替换并将 "1" 用 "11" 替换。因此压缩后字符串变为 "23321511"。
    给定一个整数 n ，返回 外观数列 的第 n 个元素。

    示例 1：
    输入：n = 4
    输出："1211"
    解释：
    countAndSay(1) = "1"
    countAndSay(2) = "1" 的行程长度编码 = "11"
    countAndSay(3) = "11" 的行程长度编码 = "21"
    countAndSay(4) = "21" 的行程长度编码 = "1211"

    示例 2：
    输入：n = 1
    输出："1"
    解释：
    这是基本情况。

    提示：
        1 <= n <= 30

    进阶：你能迭代解决该问题吗？*/
    public String countAndSay(int n) {
        String s = "1";
        if (n == 1) {
            return s;
        }
        for (int i = 0; i < n - 1; i++) {
            s = getContext1(s);
        }
        return s;
    }

    // 这个是O(N^2)
    private String getContext(String s) {
        char[] charArray = s.toCharArray();
        int times = 1;
        char c = charArray[0];
        StringBuilder builder = new StringBuilder();
        for (int i = 1; i < charArray.length; i++) {
            if (charArray[i] == c) {
                times++;
            } else {
                builder.append(times).append(c);
                c = charArray[i];
                times = 1;
            }
        }
        builder.append(times).append(c);
        return builder.toString();
    }

    // 这个是O(N)
    private String getContext1(String s) {
        int times = 1;
        char c = s.charAt(0);
        StringBuilder builder = new StringBuilder();
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == c) {
                times++;
            } else {
                builder.append(times).append(c);
                c = s.charAt(i);
                times = 1;
            }
        }
        builder.append(times).append(c);
        return builder.toString();
    }

    @Test
    public void test() {
        String s = countAndSay(4);
        log.info(s);
    }
}
